package others;

/**
 * @author pengfei.hpf
 * @date 2020/3/14
 * @verdion 1.0.0
 * 208. 实现 Trie (前缀树)
 * 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
 *
 * 示例:
 *
 * Trie trie = new Trie();
 *
 * trie.insert("apple");
 * trie.search("apple");   // 返回 true
 * trie.search("app");     // 返回 false
 * trie.startsWith("app"); // 返回 true
 * trie.insert("app");
 * trie.search("app");     // 返回 true
 * 说明:
 *
 * 你可以假设所有的输入都是由小写字母 a-z 构成的。
 * 保证所有输入均为非空字符串。
 */
public class Trie {

    TrieNode root;
    public Trie(){
        root = new TrieNode((char)0);
    }

    public void insert(String word){
        if(word == null || word.length() == 0){
            return;
        }
        TrieNode last = root;
        char[] chars = word.toCharArray();
        for(char c: chars){
            if(last.getChild(c) != null){
                last = last.getChild(c);
            } else {
                TrieNode node = new TrieNode(c);
                last.add(node);
                last = node;
            }
        }
        last.isEnd = true;
    }

    public boolean search(String word){
        if(word == null || word.length() == 0){
            return false;
        }
        TrieNode node = findLast(word);
        return node != null && node.isEnd;
    }

    public boolean startsWith(String prefix){
        if(prefix == null || prefix.length() == 0){
            return false;
        }
        TrieNode node = findLast(prefix);
        return node != null;
    }

    private TrieNode findLast(String str){
        TrieNode r = root;
        char[] chars = str.toCharArray();
        for(char c: chars){
            if(r == null){
                break;
            }
            r = r.getChild(c);
        }
        return r;
    }

    class TrieNode{
        char val;
        TrieNode[] childs;
        boolean isEnd;
        TrieNode(char c){
            val = c;
            childs = new TrieNode[26];
        }
        private void add(TrieNode node){
            childs[node.val - 'a'] = node;
        }

        private TrieNode getChild(char c){
            return childs[c- 'a'];
        }
    }
}
